import java.util.ArrayList;
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/ 
	/* Clase Laberinto: lee un archivo de texto que tiene cargada una 	*/
	/* una matriz que representa al laberinto. Luego, arma el grafo 	*/
	/* correspondiente a dicha matriz, y si este tiene camino euleriano	*/
	/* lo muestra por pantalla											*/
	/* Tomamos como precondicion que ni la entrada ni la salida del 	*/
	/* laberinto pueden situarse en ninguna de las cuatro puntas de la 	*/
	/* matriz.															*/
	/* ACLARACION: la forma del archivo es la siguiente:				*/
	/* 		numero de filas(N)											*/
	/*		numero de columnas(M)										*/
	/* 		matriz de ceros y unos de tamaño NxM						*/
	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/
public class Laberinto{
	
	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/ 
	/* leerMatriz(String nameFile):lee la matriz desde un archivo de 	*/
	/* texto cuyo nombre es pasado por parametro. Se lanza una excepcion*/
	/* si el archivo no existe											*/
	/* pre: true										 				*/
	/* pos: si el archivo existe, la matriz se inicializa           	*/
	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/	
	public static int [][] leerMatriz(String nameFile){
		Scanner fileInput;
		File inFile = new File(nameFile);
		int size = 0;
		int [][] matrix = new int [2][2];
		try{
			fileInput = new Scanner(inFile);
			size = fileInput.nextInt(); // leo la cantidad de filas y columnas
			matrix = new int [size][size];
			for(int i=0; i<size; i++){
				for(int j=0; j<size; j++){
					matrix[i][j] = fileInput.nextInt();	
				}
			}
			fileInput.close();	
		}
		catch(FileNotFoundException e){
			System.out.println(e);
		}
		return matrix;
	} 
	
	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/ 
	/* cuentaCifras(int num):retorna la cantidad de cifras que tiene un */
	/* numero entero pasado como parametro								*/
	/* pre: true										 				*/
	/* pos: retorna el calculo de las cifras que ocupa el numero		*/
	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/	
	public static int cuentaCifras(int num){
        int cifras = 0;
        if (num < 10)
			cifras = 1;
		else{ 
			if ((num >= 10) && (num < 100))
				cifras = 2;
			else{
				if ((num >= 100) && (num < 1000))
					cifras = 3;
				else
					cifras = 4;		
			}
		}
        return cifras;        
    }
    
	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/ 
	/* imprimirEspacio(int cantCifras):imprime por pantalla la cantidad	*/
	/* de espacios en blanco necesarios para representar la cifra		*/
	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/ 
    public static void imprimirEspacio(int cantCifras){
		int	espacio = 4 - cantCifras;
		for(int i=0; i<espacio; i++)
			System.out.print(" ");
	}

	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/ 
	/* imprimirMatriz(int [][] matrix,int size): imprime 	*/
	/* por pantalla el laberinto										*/
	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/	
	public static void imprimirMatriz(int [][] matrix,int size){
		System.out.println("       GRAFO REPRESENTADO EN LA MATRIZ");
		System.out.println();
		System.out.print("  ");
		for (int k=1; k<=size; k++){
			System.out.print(k);
			imprimirEspacio(cuentaCifras(k));
		}
        System.out.println();
		for (int i=0; i<size; i++){
			System.out.print((i+1)+" ");
			for (int j=0; j<size; j++){
				int num = matrix[i][j];
				System.out.print(num);
				imprimirEspacio(cuentaCifras(num));	
			}
			System.out.println();	
		}
		System.out.println();	
	}
		
	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/ 
	/* leerFilas(String nameFile): retorna la cantidad de filas que 	*/
	/* tiene la matriz representada en el archivo de texto cuyo nombre 	*/
	/* es pasado por parametro. Lanza una excepcion si el archivo no 	*/
	/* existe															*/
	/* pre: true														*/
	/* pos: si el archivo existe, retorna la cantidad de filas			*/
	/*------------------------------------------------------------------*/
	/*------------------------------------------------------------------*/
	public static int readSize(String nameFile){
		Scanner fileInput;
		File inFile = new File(nameFile);
		int size = 0;
		try{
			fileInput = new Scanner(inFile);
			size = fileInput.nextInt(); // leo la cantidad de filas	
			fileInput.close();
		}
		catch(FileNotFoundException e){
			System.out.println(e);
		}
		return size;	
	}

	public static int warshall(int [][] matrix,int size,int n1,int n2){		
		for (int k=0; k<size; k++){
			for (int i=0; i<size; i++){
				for (int j=0; j<size; j++){
					if ((matrix[i][j])>(matrix[i][k]+matrix[k][j]))
						matrix[i][j] = matrix[i][k]+matrix[k][j];
				}
			}
		}
		return matrix[n1-1][n2-1]; // en la matriz los indices son uno menos de los que paso el usuario por parametro, ya que empiezo desde cero
	}

	public static int [][] modificar (int [][] matrix, int size, int max_int){
		for (int i=0; i<size; i++){
			for (int j=0; j<size; j++){
				if (matrix[i][j] == 0)
					matrix[i][j] = max_int;				
			}
		}
		return matrix;
	}
		
	public static void main(String args[]){
		// asumo como precondicion que la matriz es cuadrada
		// y que si el costo es cero entre dos nodos n1 y n2, estos no estan conectados entre si	
		String nameFile = "Grafo2.txt"; // Aca se puede cambiar el nombre del archivo, para cambiar de grafo
		int size = readSize(nameFile);
		int [][] matriz = leerMatriz(nameFile);
		imprimirMatriz(matriz,size);
		int max_int = 9999; // asumo que 9999 es el infinito		
		matriz = modificar(matriz,size,max_int); // modificar me retorna la matriz con infinitos en donde el costo es cero
		String linea;		
		System.out.println("Ingrese el nodo de partida: ");
		linea = System.console().readLine();
		int nodo1 = Integer.parseInt( linea );
		System.out.println("Ingrese el nodo al que quiere llegar: ");
		linea = System.console().readLine();
		int nodo2 = Integer.parseInt( linea );
        int minCost = warshall(matriz,size,nodo1,nodo2);
		if (minCost == max_int) {
			System.out.println("El nodo "+ nodo1 +" no esta conectado con el nodo "+ nodo2);
		}		
		else {
			System.out.println("El costo minimo para ir del nodo "+ nodo1 +" al nodo "+ nodo2 +" es "+ minCost);
		}	
	}			
}
